import math

def BinomialCoefficient(n, k):
    return math.factorial(n) / (math.factorial(k) * math.factorial(n - k))

def GCD(a, b):
    while b != 0:
        buffer = a % b
        a = b
        b = buffer
    return abs(a)

def Coprime(a, b):
    return GCD(a, b) == 1

def BezoutIdentity(a, b):
    assert type(a) == type(0)
    assert type(b) == type(0)

    x = 0
    y = 1
    lastx = 1
    lasty = 0
    while b != 0:
        quotient = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - quotient * x, x)
        (y, lasty) = (lasty - quotient * y, y)
    return (a, lastx, lasty)

def IsPrime(a):
    assert type(a) == type(0)

    if a == 1:
        return False

    sqrta = math.ceil(math.sqrt(a))
    p = 2
    while p < sqrta:
        if a % p == 0:
            return False
        p = p + 1
    return True

def CoprimeSet(a):
    assert type(a) == type(0)

    coprime = []
    p = 1
    while p <= a:
        if Coprime(p, a):
            coprime.append(p)
        p += 1
    return coprime
